\|\\M0basl30;\M2germ35;\M9fix20;\←=90;\ε\`'10444;\F0\; \8u(z)(\{⊗z⊗\}=2;=2;)\;

4.	One - Way Functions

\J	We have already seen that oneway functions offer a solution to the login
problem when the system's password directory is insecure, and  to  the  onetime,
oneway  message  authentication problem.     They also allow the construction of
trap door questions. Their cryptographic importance is even more basic  and,  as
shown  below, the existence of oneway functions is necessary to the existence of
secure cryptosystems.   Because of their fundamental importance to cryptography,
and  because  it  seems  like  a  simpler  task,  we suggest that a proof of the
existence of oneway functions should be pursued as a first step toward  a  proof
of  the existence of secure cryptosystems. This section explores possible oneway
functions in hope of stimulating such work.
	Suppose we have a cryptosystem which is secure against a known plaintext
attack and which  operates  with  a  key  on  blocks  of  plaintext  to  produce
cryptograms.   By  using  a  fixed,  known  sequence P in place of the plaintext
block, by using X in place of the key, and by taking the resultant cryptogram to
be  Y we implement a oneway function Y = f(X) ≡ T\∪X\⊗(P). This function must be
oneway because solving for X given Y is equivalent to finding  the  key  from  a
single  known  plaintext  -  cryptogram  pair.   Public knowledge of f(.) is now
equivalent to public knowledge of {T\∪k\⊗(.)} and P.
	Thus,  the  existence of computationally secure cryptosystem implies the
existence of a oneway function. Therefore, the existence of oneway functions  is
a necessary condition for the existence of computationally secure cryptosystems.
While the convese is not necessarily true, as shown in  the  next  section  with
logs  mod  p  it is possible for a function originally found in the search for a
oneway function to yield a good cryptosystem.
	oneway functions are also basic to key generator based cryptosystems.  A
key generator is a pseudo-random bit generator whose  output  is  XOR'd  with  a
message represented in binary form, in imitation of a one time pad.   The key is
used as a "seed" which determines the pseudo random output sequence.    A  known
plaintext  attack  thus  reduces  to the problem of determining the key from the
output of the key generator. For the system to be  usable,  calculation  of  the
output  from  the  key must be computationally simple.  And for the system to be
secure, computation of the key from the output must be infeasible. Thus  a  good
key generator is, almost by definition, a oneway function.

	Use  of either of these cryptosystems as a one way function suffers from
a minor problem.      As noted earlier, if the function  f(.)  is  not  uniquely
invertible,  it  is  not  necessary  (or possible) to find the actual value of X
used.    Rather any X with the same image will suffice.  And, while each mapping
T\∪k\⊗(.)  in  a  cryptosystem must be bijective there is no such restriction on
the function f(.) defined implicitly in  ()  from  key  to  cryptogram.  Indeed,
guaranteeing  that  a  cryptosystem  has  this property appears quite difficult.
Rather, we suspect that in a good cryptosytem the mapping f(.) will tend to have
the  characteristics  of  a  randomly  chosen  mapping  (i.e.     f(X) is chosen
uniformly from all possible Y, and successive choices are independent).  In this
case,  if  X  is  chosen  uniformly  and  there  are an equal number of keys and
messages (X and Y), then the probability that the resultant Y has i inverses  is
approximately  e\∩-1\⊗  /  (i- - 1)! for i = 1, 2, 3, ...  .   This is a Poisson
distribution with mean λ=1, scaled by a factor of  i.  The  expected  number  of
inverses is thus only 2.  While it is possible for f(.) to be more degenerate, a
good cryptosystem will not be too degenrate since then the key is not being well
used.   In the worst case, if f(X) ≡ y\∪0\⊗ for some y\∪0\⊗, we have T\∪k\⊗(P) ≡
C\∪0\⊗, and encipherment of P would not depend on the key at all!
	Evans,  Kantrowitz  and  Weiss [] suggest a different way to use a block
cipher  system  to  produce  a  oneway  function.   The  suggest  that  g(X)   =
T\∪X\⊗(X)\R(  ) should be oneway.  While it probably is, we prefer the technique
() because of its equivalence to a known plaintext attack.


	The  next  candidate  for  a oneway function is a high degree polynomial
over a finite field.  That is
	Y  =  p(X),  mod q where q is a prime number and p(X) is a polynomial of
degree n.  This technique is suggested by the relative ease of evaluation of  an
nth degree polynomial when compared with solution of an nth degree equation.
	We must do the evaluation mod q for two reasons.   Most  importantly  we
must  keep the word size of the output small.  If X is a 32 bit number and n=100
we get a 3200 bit output when evaluating over the  reals.    By  evaluating  mod
q=2\∩32\⊗-5,  which  is  prime [], we ensure that Y is representable in 32 bits.
This also simplifies evaluation of p(X)  since  only  32  bit  numbers  need  be
multiplied or added.
	A second reason for using modular arithmetic is  that  polynomials  over
the reals are continuous and are therefore sesceptible to iterative solution, as
by Newton's method.   Of course, if the  solution  must  be  an  integer  to  be
acceptable in login, there is no guarantee that the root found will work.   Even
so, the "discontinuity" introduced by modular arithmetic appears attractive.
	Unfortunately,   the   intuitive   difficulty  of  solving  high  degree
polynomial equations over a finite field is somewhat  unfounded,  and  the  best
currently known algorithms require on the order of n\∩2\⊗ operations [].   Since
evaluation of an arbitrary nth degree polynomial requires  n  multiplies  and  n
additions,  at  best  the ratio of inverse to forward computation time is on the
order of n.  This is too small since we need ratios of 10\∩6\⊗, 10\∩9\⊗ or  even
greater.     To  obtain  these  large  ratios  would  require  too  much forward
computation time and, more importantly, too  much  memory  for  storage  of  the
polynomial's coefficients.
	Purdy [] suggests using sparse polynomials to circumvent  this  problem.
Yet  one  has no assurance that this small special class of polynomials which is
so much easier than usual to compute in the forward direction, is not also  much
easier to invert.  Further study of this problem is indicated.
	Finding a root of a polynomial is a special case  of  factoring  over  a
ring  [].    Rings  other  than  polynomials may prove useful and should also be
investigated.

	The  next  candidate  for  a  oneway  function comes from computational
complexity.  As discussed in the next section, any NP complete problem  is  very
strongly  believed  to  require  computation  time  which  is  exponential in a
parameter n of the problem.  One of  the  NP  complete  problems,  the  knapsack
problem, yields a oneway function if this is true.
	Let y = f(X) = a.X where a is a known vector of n integers (a1,a2,...an)
and x is a vector of n 0's and 1's.  Calculation of f is simple, involving 
summing at most n integers.  The problem of inverting f is know as the knapsack
problem and requires finding a subset of the {ai} which sum to y.
	Exhaustive search of all 2↑n subsets is computationally infeasible for
n in the range 100 to 200.  Care must be excercised, however, in selecting
the parameters of the problem to ensure that shortcuts are not possible.
For example if n=100 and each ai is 32 bits long, y is at most 39 bits long,
and f is hightly degenerate; requiring on average only 2↑38 tries to find
a solution. 
Somewhat more trivially, if ai = 2↑i-1 then inverting f is euivalent to 
finding the binary decomposition of y.
	This example demonstrates both the great promise and  the  considerable
shortcomings  of  contemporary complexity theory.  The theory only tells us that
the knapsack problem is difficult in  the  worst  case.  It  gives  no
indication of its difficulty for any particular array.

	Another possible oneway  function  is  suggested  by  the  computational
characteristics  of  sequential decoding []. As shown by Jacobs and Berlekamp []
there is a lower bound to the computation required for sequential decoding,  and
for  r  >  R\∪comp\⊗  the  expected  number  of  computations per decoded bit is
infinite.   While it is possible that there are non-sequential  techniques  with
better  computational  characteristics,  the  existence  of  a  lower  bound  on
computation  is  encouraging,  and  invites  further  study.     For   ease   of
implementation  the  "noisy"  channel  used  would  be  an erasure channel which
deterministically erases every other bit (or two out of every there, etc.). This
really  makes  the  code a convolutional compressive code [ , ], and as shown by
Koshelev[] the R\∪comp\⊗ phenomenon is still present.   The  user's  password  X
would  be a string of charactters which was meaningful (and easily checked to be
so) in some artifical language, and f(X) would be the compressed data.  So  long
as  R\∪comp\⊗  <  R  <  H,  where  H is the entropy of the language, there would
typically be a unique inverse (i.e. only one meaningful decoded sequence) yet it
would require large amounts of computation to find.  Calculation of f(X), on the
other hand, is simple and merely requires the convolutional encoding operation.
	The  last  potential  oneway function we shall discuss in exponentiation
mod q, which was suggested to  the  authors  by  Prof.  John  Gill  of  Stanford
University.

For  1 ≤ X ≤ P-1 let Y = α↑X, mod q where q is a prime integer and α is a known,
primitive element of GF(q).   For 1≤Y≤P-1  we  can  define  the  unique  inverse
X=logαY, mod q.  And while the exponentiation operation is computable in at most
2log2 q multiplications [], Knuth [] gives an algorithm which requires O(sqrt q)
operations as the best he knew for evaluating the log mod q operation ().  While
special cases have since been found [,,] in which logs mod q are  computable  in
roughly O(log 2*q) operations, for properly chosen values of q Knuth's algorithm
is still the best known.
	Taking  q  to  be  slightly  less  than  2↑100,  all quantities could be
represented as 100 bit numbers.  Calculation of Y from X would  take  about  200
operations  on  100  bit  numbers, a very reasonable requirement.   Yet, if q is
properly chosen, calculation of X from Y would take on the order of 2↑50 = 10↑15
operations  with  the  best,  currently known algorithm. If this is not adiquate
going to 200 bit numbers, would only double the forward  computation  time,  but
would square the number of operations required to invert the function to 10↑30.